// 给定一棵二叉树，按照从顶部到底部的顺序，返回从右侧能看到的节点值

// 思路：层序遍历，当遍历到一层的最后一个时记录值
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，queue的大小

function rightSideView(root) {
    if (!root) {
        return []
    }
    let result = []
    let queue = [root]
    while (queue.length) {
        let len = queue.length
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            if (i === len -1) {
                result.push(node.val)
            }  
            if (node.left) {
                queue.push(node.left)
            }          
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return result
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

console.log(rightSideView(root));